'''
https://leetcode.cn/problems/boolean-evaluation-lcci/description/
'''
from functools import cache

def eval(op, a, b):
    print(op, a, b)
    if op == '&':
        return a & b
    elif op == '|':
        return a | b
    else:
        return a ^ b


class Solution:
    def countEval(self, s: str, result: int) -> int:
        @cache
        def f(i, j):
            if i == j:
                return (1, 0) if s[i] == '0' else (0, 1)
            if i + 2 == j:
                v = eval(s[i + 1], int(s[i]), int(s[i + 2]))
                return (1, 0) if v == 0 else (0, 1)
            res0 = res1 = 0
            for m in range(i + 1, j, 2):
                a, b = f(i, m - 1)
                c, d = f(m + 1, j)
                if s[m] == '&':
                    res0 += a * c + a * d + c * b
                    res1 += b * d
                elif s[m] == '|':
                    res0 += a * c
                    res1 += a * d + c * b + b * d
                else:
                    res0 += a * c + b * d
                    res1 += a * d + c * b
            return res0, res1

        n = len(s)
        if n == 1:
            return 1 if int(s) == result else 0
        res0, res1 = f(0, n - 1)
        return res0 if result == 0 else res1

    # dp打表
    def countEval2(self, s: str, result: int) -> int:
        n = len(s)
        dp = [[[0, 0] for _ in range(n)] for _ in range(n)]
        # 第一维度依赖后边，第二维度依赖前边
        # 普遍位置依赖当前行左边多少列，下边多少行当前列   从下往上，从左往右
        # 初始位置 i,i。 以及i, i+2
        # i<=j 只填上三角
        for i in range(0, n, 2):
            # return (1, 0) if s[i] == '0' else (0, 1)
            dp[i][i][0] += s[i] == '0'
            dp[i][i][1] += s[i] == '1'
        for i in range(0, n - 2, 2):
            v = eval(s[i + 1], int(s[i]), int(s[i + 2]))
            dp[i][i + 2][0] += v == 0
            dp[i][i + 2][1] += v == 1

        for i in range(n - 5, -1, -2):
            for j in range(i + 4, n, 2):
                res0 = res1 = 0
                for m in range(i + 1, j, 2):
                    a, b = dp[i][m - 1]
                    c, d = dp[m + 1][j]
                    if s[m] == '&':
                        res0 += a * c + a * d + c * b
                        res1 += b * d
                    elif s[m] == '|':
                        res0 += a * c
                        res1 += a * d + c * b + b * d
                    else:
                        res0 += a * c + b * d
                        res1 += a * d + c * b
                dp[i][j][0] = res0
                dp[i][j][1] = res1
        return dp[0][-1][0] if result == 0 else dp[0][-1][1]


s = "1^0|0|1"
result = 0
print(Solution().countEval(s, 0))
